package LC;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author lhn
 * @date 2024-09-17 14:05
 */

public class BusRoutes {
    public static void main(String[] args) {
        int[][] busRoutes1 = {{1, 2, 7}, {3, 6, 7}};
        int source1 = 1;
        int target1 = 6;
        System.out.println(numBusesToDestination(busRoutes1, source1, target1));

//        int[][] busRoutes2 = {{7, 12}, {4, 5, 15}, {6}, {15, 19}, {9, 12, 13}};
//        int source2 = 15;
//        int target2 = 12;
//        System.out.println(numBusesToDestination(busRoutes2, source2, target2));
    }

    public static int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) return 0;
        Map<Integer, List<Integer>> map = new HashMap<>();  // 站点：路线
        boolean[][] edge = new boolean[routes.length][routes.length];   // 无向图
        for (int i = 0; i < routes.length; i++) {   //遍历公交车
            for (int site: routes[i]
                 ) {    // 遍历站点
                List<Integer> list = map.getOrDefault(site, new ArrayList<>()); // 站点中所有的路线
                for (int j : list
                     ) {    // 遍历站点对应的路线
                    edge[i][j] = edge[j][i] = true; // 有边
                }
                list.add(i);    // 添加路线
                map.put(site, list);    // 更新站点对应的路线
            }
        }
        System.out.println(map);
        for (int i = 0; i < routes.length; i++) {
            for (int j = 0; j < routes.length; j++) {
                System.out.print(edge[i][j] + " ");
            }
            System.out.println();
        }

        return 1;   //TODO
    }

}
